#include <iostream>
#include <cmath>
using namespace std;
#define DEBUG
using ll=long long;
ll n, k, ans;
int base, inde;
void solve()
{
    scanf("%lld %lld", &n, &k);
    ans=1;
    for(int base=2; 1ll*base*base<=n; base++)
    {
        inde=0;
        while(n%base==0)
            inde++, n/=base;
        if(inde>=k) ans*=pow(base, inde);
    }
    printf("%lld\n", ans);
}

signed main()
{
    #ifdef DEBUG
        freopen("../in.txt", "r", stdin);
        freopen("../out.txt", "w", stdout);
    #endif

    int T=1; scanf("%d", &T); 
    while(T--) 
    {
        solve();
    }
    return 0;
}